#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void non_recursive_merge_sort(vector<int> & a){
	for(unsigned int i=1; i < a.size(); i<<=1){
		for(unsigned int j=0; j<a.size(); j += 2*i){
			vector<int> temp;
			unsigned int k1=j;
			unsigned int k2=j+i;			
			unsigned int end1 = min(j+i, a.size());
			unsigned int end2 = min(j+2*i, a.size());

			while( k1 < end1 && k2 < end2 ){
				if(a[k1] < a[k2])
					temp.push_back(a[k1++]);
				else
					temp.push_back(a[k2++]);
			}
			while(k1<end1)
				temp.push_back(a[k1++]);
			while(k2< end2)
				temp.push_back(a[k2++]);

			for(unsigned int k=j;k<end2;k++){
				a[k] = temp[k-j];
			}
		}
	}
}

int main()
{
	vector<int> vec;
	vec.push_back(2);
	vec.push_back(4);
	vec.push_back(6);
	vec.push_back(1);
	vec.push_back(3);
	vec.push_back(5);
	vec.push_back(-1);
	vec.push_back(-3);
	vec.push_back(-5);


	non_recursive_merge_sort(vec);

	for(vector<int>::const_iterator i=vec.begin();i!=vec.end(); ++i)
		cout<<*i<<endl;
	return 0;
}
